class Solution
{
public:
    int mostFrequentPrime(vector<vector<int>> &mat)
    {
        if (isPrime.empty())
        {
            initIsPrime();
        }

        unordered_map<int, int> nums;
        vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        int m = mat.size(), n = mat[0].size();
        for (int startX = 0; startX < m; startX++)
        {
            for (int startY = 0; startY < n; startY++)
            {
                for (auto &direction : directions)
                {
                    int x = startX, y = startY;
                    int num = 0;
                    while (x >= 0 && x < m && y >= 0 && y < n)
                    {
                        num = num * 10 + mat[x][y];
                        nums[num]++;
                        x += direction[0];
                        y += direction[1];
                    }
                }
            }
        }

        int maxFreq = -1;
        int maxFreqNum = -1;
        for (auto &[num, freq] : nums)
        {
            if (num > 10 && isPrime[num])
            {
                if (freq > maxFreq)
                {
                    maxFreq = freq;
                    maxFreqNum = num;
                }
                else if (freq == maxFreq)
                {
                    maxFreqNum = max(maxFreqNum, num);
                }
            }
        }
        return maxFreqNum;
    }

    static vector<int> isPrime;
    static void initIsPrime()
    {
        isPrime = vector<int>(1000001, 1);
        isPrime[0] = isPrime[1] = 0;
        for (int i = 2; i <= 1000000; i++)
        {
            if (isPrime[i])
            {
                for (int j = i * 2; j <= 1000000; j += i)
                {
                    isPrime[j] = 0;
                }
            }
        }
    }
};

vector<int> Solution::isPrime{};